package com.company.algo.DP.subseqProblem.DiscontinuousSubsequences;

import java.util.Arrays;

/**300.最⻓递增⼦序列
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
 * 定义：dp[i]表示位置i之前包括i的LIS长度
 * 转移：对于j<i,if(nums[i]>nums[j]) dp[i] = max(dp[i], dp[j] + 1)
 * else dp[i] = dp[i-1]
 * 顺序：从前往后
 * 初始值：i>0,dp[i]=1,至少LIS长度为1
 */
public class LengthOfLIS {
    public int lengthOfLIS1(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res,dp[i]);
        }
        return dp[nums.length-1];
    }

    //贪心加二分
    //构建一个新的列表，存储递增的子序列
    /*
    1. 在遍历数组 nums 的过程中，看到一个新数 num，如果这个数 严格 大于有序数组 tail 的最后一个元素，
    就把 num 放在有序数组 tail 的后面，否则进入第 2 点；
    2. 在有序数组 tail 中查找第 1 个等于大于 num 的那个数，试图让它变小；
     */
    public int lengthOfLIS(int[] nums) {
        int len = nums.length;
        if(len < 2) return len;
        int[] tail = new int[len];
        tail[0] = nums[0];
        int end = 0;
        for(int i = 1; i < len; i++){
            if(nums[i]>tail[end]) tail[++end] = nums[i];
            else{
                int left = 0, right = end;
                int target = nums[i];
                while(left < right){
                    int mid = (left + right)/2;
                    if(tail[mid] < target) left = mid + 1;
//                    else right = mid - 1;
                    else right = mid;       //找到第一个大于等于target的数
                }
                tail[left] = target;
            }
            System.out.println(Arrays.toString(tail));
        }
        return end+1;
    }

    public static void main(String[] args) {
        LengthOfLIS Main = new LengthOfLIS();
        int[] nums = {3,5,6,2,5,4,19,5,6,7,12};
        System.out.println(Main.lengthOfLIS(nums));
    }
}
